package org.example.everyday;

import java.util.*;

public class Lc2039 {
    public static void main(String[] args) {
       Lc2039 lc2039 = new Lc2039();
       int[][] edges = {{0,1},{1,2},{1,3}};
       int[] patience = {0,2,1};
       lc2039.networkBecomesIdle(edges,patience);
    }
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Map<Integer,Integer> nodeToDist = getNodeToDist(edges);
        int ans = 0;
        for(int i = 1; i < patience.length; i++){
            int dist = nodeToDist.get(i);
            int extra = (2 * dist - 1) / patience[i];
            int time = 2 * dist + extra * patience[i];
            ans = Math.max(ans,time);

        }

        return  ans + 1;
    }

    /**
     * dfs
     * @param edges
     * @return
     */
    private Map<Integer,Integer> getNodeToDist(int[][] edges){
        Map<Integer,Integer> ans = new HashMap<>();
        Queue<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();

        Map<Integer,Set<Integer>> graph = getGraph(edges);
        queue.offer(0);
        visited.add(0);
        int dist = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size-- > 0){
                int cur = queue.poll();
                ans.put(cur,dist);
                for(int next : graph.getOrDefault(cur,new HashSet<>())){
                    if(visited.add(next)){
                        queue.offer(next);
                    }
                }
            }
            dist++;
        }
        return ans;
    }

    private Map<Integer, Set<Integer>> getGraph(int[][] edges) {
        Map<Integer, Set<Integer>> ans = new HashMap<>();
        for (int[] edge : edges){
            ans.putIfAbsent(edge[0],new HashSet<>());
            ans.get(edge[0]).add(edge[1]);
            ans.putIfAbsent(edge[1],new HashSet<>());
            ans.get(edge[1]).add(edge[0]);
        }
        return ans;
    }


}
